package Algorithm.Search.BinarySearchAndVariant.Fibonacci;

import Algorithm.Search.BasicSearch.BasicSearchWithRepetition;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Example {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int number = sc.nextInt();
        System.out.println(fibonacciSearch(arr, number));
    }
    public static boolean fibonacciSearch(int[] arr, int n) {
        int[] fibonacci = fibonacci(arr);
        int[] newArr = handleArr(arr, Arrays.copyOf(arr, fibonacci[fibonacci.length - 1]));
        int max = newArr.length - 1;
        int min = 0;
        int index = fibonacci.length - 1;
        while (min <= max) {
            int mid = min + fibonacci[index - 1] - 1;
            if(newArr[mid] == n)
                return true;
            else if(newArr[mid] < n){
                min = mid + 1;
                index--;
            } else {
                max = mid - 1;
                index -= 2;
            }
        }
        return false;
    }
    public static int[] handleArr(int[] arr, int[] newArr) {
        if(arr.length < newArr.length){
            for (int i = arr.length; i < newArr.length; i++) {
                newArr[i] = arr[arr.length - 1];
            }
        }
        return newArr;
    }
    public static int[] fibonacci(int[] arr){
        int num1 = 1;
        int num2 = 1;
        ArrayList<Integer> fibonacciList = new ArrayList<>();
        fibonacciList.add(num1);
        fibonacciList.add(num2);
        while(num2 < arr.length){
            int temp = num1;
            num1 += num2;
            num2 = temp;
            fibonacciList.add(num1);
        }
        return BasicSearchWithRepetition.ArrayListToArray(fibonacciList);
    }
}
